package leetcode.L79;

class Solution1 {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                check(board, visited, i, j, word, 0);
                if (flag) {//剪枝
                    return true;
                }
            }
        }
        return false;
    }

    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    boolean flag=false;

    public void check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return;
        } else if (k == s.length() - 1) {
            flag=true;
            return;
        }
        visited[i][j] = true;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];//检查新的方向
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {//判断
                if (!visited[newi][newj]) {//标记数组防止重复访问
                    check(board, visited, newi, newj, s, k + 1);
                }
            }
        }
        visited[i][j] = false;
    }
}